`:top

In `F33f`_`[mathematics`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Mathematics]`_`f and `F33f`_`[computer science`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_science]`_`f, a `!balanced Boolean function`! is a `F33f`_`[Boolean function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Boolean_function]`_`f whose output yields as many `!0`!s as `!1`!s over its `F33f`_`[input set`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Domain_of_a_function]`_`f. This means that for a uniformly random input string of bits, the probability of getting a `!1`! is 1/2.`:cite-ref-bsw-1-0[`F5bf`_`[1`#cite-note-bsw-1]`_`f]

>>Contents

• `F0af`_`[Examples`#examples]`_`f

• `F0af`_`[Application`#application]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>Examples

Examples of balanced Boolean functions are the `F33f`_`[majority function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Majority_function]`_`f,`:cite-ref-bsw-1-1[`F5bf`_`[1`#cite-note-bsw-1]`_`f] the "dictatorship function" that copies the first bit of its input to the output,`:cite-ref-bsw-1-2[`F5bf`_`[1`#cite-note-bsw-1]`_`f] and the `F33f`_`[parity check`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Parity_check]`_`f function that produces the `F33f`_`[exclusive or`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Exclusive_or]`_`f of the input bits.`:cite-ref-ch-2-0[`F5bf`_`[2`#cite-note-ch-2]`_`f]

If f {\\displaystyle f} is a `F33f`_`[bent function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bent_function]`_`f on n {\\displaystyle n} bits, and α α {\\displaystyle \\alpha } is any nonzero vector of n {\\displaystyle n} bits, then the function that maps x {\\displaystyle x} to f ( x ) ⊕ ⊕ f ( x ⊕ ⊕ α α ) {\\displaystyle f(x)\\oplus f(x\\oplus \\alpha )} is balanced. The bent functions are exactly the functions for which this is true, for all nonzero choices of α α {\\displaystyle \\alpha } .`:cite-ref-szz-3-0[`F5bf`_`[3`#cite-note-szz-3]`_`f]

The dictatorship function can be evaluated after examining only a single bit of the input, but that bit must always be examined. Benjamini, Schramm, and Wilson describe a more complex example based on `F33f`_`[percolation theory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Percolation_theory]`_`f with the property that a randomized `F33f`_`[Las Vegas algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Las_Vegas_algorithm]`_`f can compute the function exactly while ensuring that the probability of reading any particular input bit is small, roughly inversely proportional to the square root of the number of bits.`:cite-ref-bsw-1-3[`F5bf`_`[1`#cite-note-bsw-1]`_`f]

>>Application

Balanced Boolean functions are used in `F33f`_`[cryptography`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cryptography]`_`f, where being balanced is one of "the most important criteria for cryptographically strong Boolean functions".`:cite-ref-szz-3-1[`F5bf`_`[3`#cite-note-szz-3]`_`f] If a function is not balanced, it will have a `F33f`_`[statistical bias`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Statistical_bias]`_`f, making it subject to `F33f`_`[cryptanalysis`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cryptanalysis]`_`f such as the `F33f`_`[correlation attack`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Correlation_attack]`_`f.

>>References

`:cite-note-bsw-1`!1.`! `F0af`_`[↑`#cite-ref-bsw-1-0]`_`f `:citerefbenjaminischrammwilson2005`a`F33f`_`[Benjamini, Itai`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Itai_Benjamini]`_`f; `F33f`_`[Schramm, Oded`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Oded_Schramm]`_`f; Wilson, David Bruce (2005), "Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read", in Gabow, Harold N.; Fagin, Ronald (eds.), `*Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22–24, 2005`*, Association for Computing Machinery, pp. 244–250, `F33f`_`[arXiv`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ArXiv_(identifier)]`_`f:math.PR/0410282, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1145/1060590.1060627, `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 1-58113-960-8

`:cite-note-ch-2`!2.`! `F0af`_`[↑`#cite-ref-ch-2-0]`_`f `:citerefchakrabartyhayes1998`aChakrabarty, K.; Hayes, J.P. (1998), "Balanced Boolean functions", `*IEE Proceedings - Computers and Digital Techniques`*, `!145`! (1): 52, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1049/ip-cdt:19981769 (inactive 11 July 2025)`B100`F9d9{{citation}}`f`b: CS1 maint: DOI inactive as of July 2025 (link)

`:cite-note-szz-3`!3.`! `F0af`_`[↑`#cite-ref-szz-3-0]`_`f `:citerefseberryzhangzheng1993`a`F33f`_`[Seberry, Jennifer`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Jennifer_Seberry]`_`f; Zhang, Xian-Mo; Zheng, Yuliang (1993), "Nonlinearly balanced Boolean functions and their propagation characteristics", in Stinson, Douglas R. (ed.), `*Advances in Cryptology – CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22–26, 1993, Proceedings`*, Lecture Notes in Computer Science, vol. 773, Springer, pp. 49–60, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/3-540-48329-2_5, `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-3-540-57766-9

`c`F0af`_`[↑ Back to top`#top]`_`f`a